1. Field
The present invention relates generally to digital communications systems, and more specifically to a method and hardware architecture for parallel pruned bit-reversal interleaving.
2. Background
Communication systems use numerous techniques to increase the amount of information transferred while minimizing transmission errors. In these communication systems, the information is typically represented as a sequence of binary bits or blocks of bits called frames. The binary information is modulated to signal waveforms and transmitted over a communication channel. Communication channels tend to introduce noise and interference that corrupt the transmitted signal. At a receiver the received information may be corrupted and is an estimate of the transmitted binary information. The number of bit errors or frame errors depends on the amount of noise and interference in the communication channel.
To counter the effects of transmission channel corruption, channel interleaving error correction coding is often used in digital communication systems to protect the digital information from noise and interference and reduce the number of bit/frame errors. Channel interleaving is employed in most modern wireless communications systems to protect against burst errors. A channel interleaver reshuffles encoded symbols in such a way that consecutive symbols are spread apart from each other as far as possible in order to break the temporal correlation between successive symbols involved in a burst of errors. A reverse de-interleaving operation is performed at the receiver side before feeding the symbols to a channel decoder. Typically, these interleavers employ some form of bit-reversal operations in generating the interleaved addresses, and have a programmable size to accommodate for various encoded packet lengths. In one scheme, a pruned bit-reversal channel interleaver in its physical layer to interleave any packet of a length that is a multiple of 8. In pruned bit-reversal interleaving, a packet of size N is interleaved by mapping n-bit linear addresses into n-bit bit-reversed addresses, where n is the smallest integer such that N≦2n. Linear addresses that map to addresses outside [0, N−1] are invalid addresses, which are pruned out.
Traditionally, interleavers and their architectures have been employed in turbo codes Bit-reversal mapping has been mainly applied to reduce row conflicts, improve hit-rates in SDRAM applications, and to improve the shuffle permutation stages of the Fast Fourier Transform (FFT) algorithm. In turbo interleavers, emphasis has been placed on reducing interleaving latency by avoiding memory collisions of read/write operations by the constituent (MAP) decoders. Such software programmable turbo interleavers for multiple 3G wireless standards are known.
PBRI interleavers have not traditionally been applied to channel interleavering because, despite their simplicity, interleaved addresses must be sequentially generated. In order to generate the interleaved address of a linear address x, the interleaved addresses of all linear addresses less than x must first be generated. This follows from the fact that the number of pruned addresses that have occurred before x must be known in order to know where to map x. This requirement introduces a serial latency bottleneck. Serial bottlenecks can be especially disadvantageous when (de-)interleaving long packets.
There is therefore a need in the art for an algorithm that efficiently determines any interleaved addresses and eliminates addressing dependency. Moreover, there is a need for the algorithm to have an easily implemented architecture that can be constructed using basic logic gates with a short critical path delay.